package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/28 8:45
 */
public class C633 {


    // 枚举所有可能
    public static boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {     // long防止整型溢出
            double b = Math.sqrt(c - a * a);
            if (b == (int) b) {
                return true;
            }
        }
        return false;
    }

    // 左右指针
    public static boolean judgeSquareSum2(int c) {
        int a = 0, b = (int) Math.sqrt(c);  // 假设 a是偏小的 b是偏大的
        int sum;
        while (a <= b) {
            sum = a * a + b * b;
            if (sum == c) return true;
            else if (sum <= c) a++;
            else b--;
        }
        return false;
    }

    // 数学法， 证明： https://wstein.org/edu/124/lectures/lecture21/lecture21/node2.html
    public static boolean judgeSquareSum3(int c) {
        for (int base = 2; base * base <= c; base++) {
            // 如果不是因子，枚举下一个
            if (c % base != 0) {
                continue;
            }

            // 计算 base 的幂
            int exp = 0;
            while (c % base == 0) {
                c /= base;
                exp++;
            }

            // 根据 Sum of two squares theorem 验证
            if (base % 4 == 3 && exp % 2 != 0) {
                return false;
            }
        }

        // 例如 11 这样的用例，由于上面的 for 循环里 base * base <= c ，base == 11 的时候不会进入循环体
        // 因此在退出循环以后需要再做一次判断
        return c % 4 != 3;
    }


    // for test
    public static void main(String[] args) {
        int c = 5;
        System.out.println(judgeSquareSum(c));
    }

}
